package com.fs.leetcode.lianbiao;


    /**
     * 思路：采用tail+head添加尾结点操作多，性能会提升
     *
     * 1、定义链表 val, next
     * 2、定义全局变量head,  size
     * 根据索引获取：
     *    在链表范围外的退出
     *    定义一个链表将头指针指向链表， 遍历链表 node = node.next
     *
     * 添加思路：
     *    添加到链表头部
     *      链表为空直接 将该指正指向head
     *      不为空  node.next = head; head = node;
     *
     *    添加到链表尾部
     *       将指针移动到链表尾部，将新元素添加到尾部  tail.next = new Link(val);
     *
     *    添加到链表的指定位置
     *       链表为空添加到头结点
     *
     *      查找要插入节点的前一个节点的位置
     *      pre.next = node;  node.next = pre.next.next;
     *
     * 删除链表：
     *     查找要插入节点的前一个节点的位置
     *     pre.next = pre.next.next;
     *
     */
public class MyLinkedList {

    private  Integer size;
    LinkedListNode head;
    public MyLinkedList() {

    }
    public int get(int index) {
       if(size < 0 && index >=size){
           return -1;
       }
        LinkedListNode node = head;
       for(int i =0;i<index;i++){
           node = node.next;
       }

       return node.val;
    }
    public void addAtHead(int val) {
        LinkedListNode node = new LinkedListNode(val);
        if(head == null){
            head = node;
        }else{
            node.next = head;
            head = node;
        }
        size ++;
    }
    public void addAtTail(int val) {
        // 无原因，添加到头
        if (size == 0) {
            addAtHead(val);
            return;
        }
        LinkedListNode tail = head;
        while (true){
            if(tail.next == null){
                break;
            }
            tail = tail.next;
        }
        tail.next = new LinkedListNode(val);
        size ++;
    }
    //查找的是前一节点
    public void addAtIndex(int index, int val) {
        if(index <=0){
            addAtHead(val);
        }

        LinkedListNode pre = head;
        for(int i = 0;i<index;i++){
            pre = pre.next;
        }

        LinkedListNode node = new LinkedListNode(val);
        pre.next = node;
        node.next = pre.next.next;
        size ++;
    }

    public void deleteAtIndex(int index) {
        if(index == 0){
            head = head.next;
        }else {
            LinkedListNode pre = head;
            for(int i = 0;i<index;i++){
                pre = pre.next;
            }
            pre.next = pre.next.next;
        }
    }

    class LinkedListNode{
        Integer val;
        LinkedListNode next;

        public  LinkedListNode(Integer s){
            LinkedListNode node = new LinkedListNode(0);
        }
    }
}
